package com.mlh.matrix;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/8/19 15:51
 * @DESCRIPTION
 */
// 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
// 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
// 输出：[1,2,3,6,9,8,7,4,5]
public class 螺旋矩阵 {
    public List<Integer> method1(int[][] matrix) {
        int rowLen = matrix.length, colLen = matrix[0].length;
        boolean[][] aux = new boolean[rowLen][colLen];//辅助数组来记录已遍历的元素
        int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 代表4个方向
        int curDirection = 0;// 表示当前方向
        int total = rowLen * colLen;// 用于结束循环，将矩阵中所有的元素都遍历了一遍
        List<Integer> res = new LinkedList<>();
        int row = 0, col = 0;
        for (int i = 0; i < total; i++) {
            res.add(matrix[row][col]);
            aux[row][col] = true;
            int nextRow = row + direction[curDirection][0], nextCol = col + direction[curDirection][1];
            //判断下一步是否符合条件，不符合条件则改变方向
            if (nextRow >= rowLen || nextRow < 0
                    || nextCol >= colLen || nextCol < 0
                    || aux[nextRow][nextCol]) {
                curDirection = (curDirection + 1) % 4;
            }
            row += direction[curDirection][0];
            col += direction[curDirection][1];
        }
        return res;
    }

    //其实这题有点意思
    //方向二维数组化 走过利用辅助数组记录  改变方向利用取模
    public List<Integer> practice(int[][] matrix) {
        int rowLen=matrix.length,colLen=matrix[0].length;
        boolean[][] aux = new boolean[rowLen][colLen];
        int[][]directions={{0,1},{1,0},{0,-1},{-1,0}};
        int curDirection=0;
        List<Integer>res=new ArrayList<>();
        int row=0,col=0;
        for (int i = 0; i < rowLen*colLen; i++) {
            res.add(matrix[row][col]);
            aux[row][col]=true;
            int nextRow=row+directions[curDirection][0],nextCol=col+directions[curDirection][1];
            if(nextRow>=rowLen||nextCol>=colLen||nextRow<0||nextCol<0||aux[nextRow][nextCol]){
                //改变方向
                curDirection=(curDirection+1)%4;
            }
            row+=directions[curDirection][0];
            col+=directions[curDirection][1];
        }
        return res;
    }
}
